{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random,datetime\n",
    "from bisect import bisect_left\n",
    "from math import exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Resource:\n",
    "    def __init__(self, name, value, weight, volume):\n",
    "        self.Name = name\n",
    "        self.Value = value\n",
    "        self.Weight = weight\n",
    "        self.Volume = volume"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "items = [Resource(\"面粉\", 1680, 0.265, .41),\n",
    "        Resource(\"黄油\", 1440, 0.5, .13),\n",
    "        Resource(\"糖\", 1840, 0.441, .29)]\n",
    "maxWeight = 10\n",
    "maxVolume = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ItemQuantity:\n",
    "    def __init__(self, item, quantity):\n",
    "        self.Item = item\n",
    "        self.Quantity = quantity\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.Item == other.Item and self.Quantity == other.Quantity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Fitness:\n",
    "    def __init__(self, totalWeight, totalVolume, totalValue):\n",
    "        self.TotalWeight = totalWeight\n",
    "        self.TotalVolume = totalVolume\n",
    "        self.TotalValue = totalValue\n",
    "\n",
    "    def __gt__(self, other):\n",
    "        if self.TotalValue != other.TotalValue:\n",
    "            return self.TotalValue > other.TotalValue\n",
    "        if self.TotalWeight != other.TotalWeight:\n",
    "            return self.TotalWeight < other.TotalWeight\n",
    "        return self.TotalVolume < other.TotalVolume\n",
    "\n",
    "    def __str__(self):\n",
    "        return \"重量: {:0.2f} 容积: {:0.2f} 价值: {}\".format(\n",
    "            self.TotalWeight,\n",
    "            self.TotalVolume,\n",
    "            self.TotalValue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KnapsackProblemData:\n",
    "    def __init__(self):\n",
    "        self.Resources = []\n",
    "        self.MaxWeight = 0\n",
    "        self.Solution = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Window:\n",
    "    def __init__(self, minimum, maximum, size):\n",
    "        self.Min = minimum\n",
    "        self.Max = maximum\n",
    "        self.Size = size\n",
    "\n",
    "    def slide(self):\n",
    "        self.Size = self.Size - 1 if self.Size > self.Min else self.Max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Chromosome:\n",
    "    def __init__(self, genes, fitness):\n",
    "        self.Genes = genes\n",
    "        self.Fitness = fitness\n",
    "        self.Age = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_fitness(genes):\n",
    "    totalWeight = 0\n",
    "    totalVolume = 0\n",
    "    totalValue = 0\n",
    "    for iq in genes:\n",
    "        count = iq.Quantity\n",
    "        totalWeight += iq.Item.Weight * count\n",
    "        totalVolume += iq.Item.Volume * count\n",
    "        totalValue += iq.Item.Value * count\n",
    "\n",
    "    return Fitness(totalWeight, totalVolume, totalValue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def display(candidate, startTime):\n",
    "    timeDiff = datetime.datetime.now() - startTime\n",
    "    genes = candidate.Genes[:]\n",
    "    genes.sort(key=lambda iq: iq.Quantity, reverse=True)\n",
    "\n",
    "    descriptions = [str(iq.Quantity) + \" x \" + iq.Item.Name for iq in genes]\n",
    "    if len(descriptions) == 0:\n",
    "        descriptions.append(\"Empty\")\n",
    "    print(\"{}\\t{}\\t{}\".format(\n",
    "        ', '.join(descriptions),\n",
    "        candidate.Fitness,\n",
    "        timeDiff))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add(genes, items, maxWeight, maxVolume):\n",
    "    usedItems = {iq.Item for iq in genes}\n",
    "    item = random.choice(items)\n",
    "    while item in usedItems:\n",
    "        item = random.choice(items)\n",
    "\n",
    "    maxQuantity = max_quantity(item, maxWeight, maxVolume)\n",
    "    return ItemQuantity(item, maxQuantity) if maxQuantity > 0 else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutate(genes, items, maxWeight, maxVolume, window):\n",
    "    #滑动窗口\n",
    "    window.slide()\n",
    "    #首先计算传入的父本基因的健壮性\n",
    "    fitness = get_fitness(genes)\n",
    "    # 计算本次进化，还可以使用的剩余重量和容积\n",
    "    remainingWeight = maxWeight - fitness.TotalWeight\n",
    "    remainingVolume = maxVolume - fitness.TotalVolume\n",
    "    \n",
    "    # 用目前父本基因的数量+10分之一的概率，来控制是否要进行移动窗口赋值\n",
    "    removing = len(genes) > 1 and random.randint(0, 10) == 0\n",
    "    # 如果父本基因数量大于1，而且随机概率90%的话\n",
    "    # 从父本基因里面随机挑选一个物品，然后把重量和容积累加给背包剩余的空间\n",
    "    # 接下去把这个物品从基因库中移除掉\n",
    "    if removing:\n",
    "        index = random.randrange(0, len(genes))\n",
    "        iq = genes[index]\n",
    "        item = iq.Item\n",
    "        remainingWeight += item.Weight * iq.Quantity\n",
    "        remainingVolume += item.Volume * iq.Quantity\n",
    "        del genes[index]\n",
    "    # 如果剩余空间还有，而且基因库中的物品数量已经等于0\n",
    "    # 或者基因库中的物品数量小于背包里面的物品数量，\n",
    "    # 并且获得百分之一的概率\n",
    "    # 这个变量用于控制，是否还要往包里面增加物品的。\n",
    "    adding = (remainingWeight > 0 or remainingVolume > 0) and \\\n",
    "             (len(genes) == 0 or\n",
    "              (len(genes) < len(items) and random.randint(0, 100) == 0))\n",
    "    \n",
    "    # 如果背包里面还可以塞东西，则直接把物品add到基因组中\n",
    "    if adding:\n",
    "        newGene = add(genes, items, remainingWeight, remainingVolume)\n",
    "        if newGene is not None:\n",
    "            genes.append(newGene)\n",
    "            return\n",
    "\n",
    "    # 随机在基因组里面挑选一件物品，加入到背包中\n",
    "    index = random.randrange(0, len(genes))\n",
    "    iq = genes[index]\n",
    "    item = iq.Item\n",
    "    remainingWeight += item.Weight * iq.Quantity\n",
    "    remainingVolume += item.Volume * iq.Quantity\n",
    "    \n",
    "    # 是否要改变基因库\n",
    "    # 如果基因组的数量小于基因库中是数量，而且符合25%的概率\n",
    "    # 从基因库里面选择更多的物品填入背包中\n",
    "    # 此过程主要是控制背包里面尽量所有的物品都要有，而不仅是一个类别的物品\n",
    "    changeItem = len(genes) < len(items) and random.randint(0, 4) == 0\n",
    "    if changeItem:\n",
    "        itemIndex = items.index(iq.Item)\n",
    "        start = max(1, itemIndex - window.Size)\n",
    "        stop = min(len(items) - 1, itemIndex + window.Size)\n",
    "        item = items[random.randint(start, stop)]\n",
    "    # 计算重量，如果还没有填满，则把这个物品加入到背包里面去\n",
    "    # 否则把这个物品从背包里面删掉。\n",
    "    maxQuantity = max_quantity(item, remainingWeight, remainingVolume)\n",
    "    if maxQuantity > 0:\n",
    "        genes[index] = ItemQuantity(item, maxQuantity\n",
    "        if window.Size > 1 else random.randint(1, maxQuantity))\n",
    "    else:\n",
    "        del genes[index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "optimal = get_fitness(\n",
    "            [ItemQuantity(items[0], 1),\n",
    "             ItemQuantity(items[1], 14),\n",
    "             ItemQuantity(items[2], 6)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_quantity(item, maxWeight, maxVolume):\n",
    "    return min(int(maxWeight / item.Weight)\n",
    "               if item.Weight > 0 else sys.maxsize,\n",
    "               int(maxVolume / item.Volume)\n",
    "               if item.Volume > 0 else sys.maxsize)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create(items, maxWeight, maxVolume):\n",
    "    genes = []\n",
    "    remainingWeight, remainingVolume = maxWeight, maxVolume\n",
    "    for i in range(random.randrange(1, len(items))):\n",
    "        newGene = add(genes, items, remainingWeight, remainingVolume)\n",
    "        if newGene is not None:\n",
    "            genes.append(newGene)\n",
    "            remainingWeight -= newGene.Quantity * newGene.Item.Weight\n",
    "            remainingVolume -= newGene.Quantity * newGene.Item.Volume\n",
    "    return genes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _mutate_custom(parent, custom_mutate, get_fitness):\n",
    "    childGenes = parent.Genes[:]\n",
    "    custom_mutate(childGenes)\n",
    "    fitness = get_fitness(childGenes)\n",
    "    return Chromosome(childGenes, fitness)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_best(get_fitness, targetLen, optimalFitness, geneSet, display,\n",
    "             custom_mutate=None, custom_create=None, maxAge=None):\n",
    "    if custom_mutate is None:\n",
    "        def fnMutate(parent):\n",
    "            return _mutate(parent, geneSet, get_fitness)\n",
    "    else:\n",
    "        def fnMutate(parent):\n",
    "            return _mutate_custom(parent, custom_mutate, get_fitness)\n",
    "\n",
    "    if custom_create is None:\n",
    "        def fnGenerateParent():\n",
    "            return _generate_parent(targetLen, geneSet, get_fitness)\n",
    "    else:\n",
    "        def fnGenerateParent():\n",
    "            genes = custom_create()\n",
    "            return Chromosome(genes, get_fitness(genes))\n",
    "\n",
    "    for improvement in _get_improvement(fnMutate, fnGenerateParent, maxAge):\n",
    "        display(improvement)\n",
    "        if not optimalFitness > improvement.Fitness:\n",
    "            return improvement\n",
    "\n",
    "\n",
    "def _get_improvement(new_child, generate_parent, maxAge):\n",
    "    parent = bestParent = generate_parent()\n",
    "    yield bestParent\n",
    "    historicalFitnesses = [bestParent.Fitness]\n",
    "    while True:\n",
    "        child = new_child(parent)\n",
    "        if parent.Fitness > child.Fitness:\n",
    "            if maxAge is None:\n",
    "                continue\n",
    "            parent.Age += 1\n",
    "            if maxAge > parent.Age:\n",
    "                continue\n",
    "            index = bisect_left(historicalFitnesses, child.Fitness, 0,\n",
    "                                len(historicalFitnesses))\n",
    "            proportionSimilar = index / len(historicalFitnesses)\n",
    "            if random.random() < exp(-proportionSimilar):\n",
    "                parent = child\n",
    "                continue\n",
    "            bestParent.Age = 0\n",
    "            parent = bestParent\n",
    "            continue\n",
    "        if not child.Fitness > parent.Fitness:\n",
    "            child.Age = parent.Age + 1\n",
    "            parent = child\n",
    "            continue\n",
    "        child.Age = 0\n",
    "        parent = child\n",
    "        if child.Fitness > bestParent.Fitness:\n",
    "            bestParent = child\n",
    "            yield bestParent\n",
    "            historicalFitnesses.append(bestParent.Fitness)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fill_knapsack():\n",
    "    startTime = datetime.datetime.now()\n",
    "    window = Window(1,\n",
    "                        max(1, int(len(items) / 3)),\n",
    "                        int(len(items) / 2))\n",
    "\n",
    "    sortedItems = sorted(items, key=lambda item: item.Value)\n",
    "\n",
    "    def fnDisplay(candidate):\n",
    "        display(candidate, startTime)\n",
    "\n",
    "    def fnGetFitness(genes):\n",
    "        return get_fitness(genes)\n",
    "\n",
    "    def fnCreate():\n",
    "        return create(items, maxWeight, maxVolume)\n",
    "\n",
    "    def fnMutate(genes):\n",
    "        mutate(genes, sortedItems, maxWeight, maxVolume, window)\n",
    "\n",
    "    best = get_best(fnGetFitness, None, optimal, None,\n",
    "                                fnDisplay, fnMutate, fnCreate, maxAge=50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13 x 糖\t重量: 5.73 容积: 3.77 价值: 23920\t0:00:00\n",
      "10 x 糖, 2 x 面粉, 2 x 黄油\t重量: 5.94 容积: 3.98 价值: 24640\t0:00:00.002989\n",
      "9 x 糖, 6 x 黄油\t重量: 6.97 容积: 3.39 价值: 25200\t0:00:00.004021\n",
      "9 x 糖, 8 x 黄油\t重量: 7.97 容积: 3.65 价值: 28080\t0:00:00.004021\n",
      "10 x 糖, 8 x 黄油\t重量: 8.41 容积: 3.94 价值: 29920\t0:00:00.004984\n",
      "12 x 黄油, 7 x 糖\t重量: 9.09 容积: 3.59 价值: 30160\t0:00:00.004984\n",
      "13 x 黄油, 7 x 糖\t重量: 9.59 容积: 3.72 价值: 31600\t0:00:00.005983\n",
      "15 x 黄油, 4 x 糖, 2 x 面粉\t重量: 9.79 容积: 3.93 价值: 32320\t0:00:00.021939\n",
      "15 x 黄油, 5 x 糖, 1 x 面粉\t重量: 9.97 容积: 3.81 价值: 32480\t0:00:00.042882\n",
      "15 x 黄油, 5 x 糖, 1 x 面粉\t重量: 9.97 容积: 3.81 价值: 32480\t0:00:00.178553\n",
      "14 x 黄油, 6 x 糖, 1 x 面粉\t重量: 9.91 容积: 3.97 价值: 32880\t0:00:00.184537\n",
      "14 x 黄油, 6 x 糖, 1 x 面粉\t重量: 9.91 容积: 3.97 价值: 32880\t0:00:00.383970\n"
     ]
    }
   ],
   "source": [
    "fill_knapsack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
